package uestc.lj.basic.listnode;

/**
 * 判断一个链表是否是回文链表
 * 1. 栈
 * 2. 快慢指针
 *
 * @Author:Crazlee
 * @Date:2021/11/22
 */
public class Code03_IsPalindromeList {
	public static class Node {
		public int value;
		public Node next;

		public Node(int data) {
			this.value = data;
		}
	}

	public static Boolean isPalindromeList(Node head) {
		if (head == null || head.next == null) {
			return true;
		}
		Node slow = head;
		Node fast = head;
		while (slow.next != null && fast.next.next != null) {
			slow = slow.next;
			fast = fast.next.next;
		}
		//将后半部分逆序
		fast = slow.next;
		slow.next = null;
		Node temp = null;
		while (fast != null) {
			temp = fast.next;
			fast.next = slow;
			slow = fast;
			fast = temp;
		}
		//判断是否是回文链表
		temp = slow;
		fast = head;
		boolean result = true;
		while (slow != null && fast != null) {
			if (slow.value != fast.value) {
				result = false;
				break;
			}
			slow = slow.next;
			fast = fast.next;
		}
		//返回之前将右半部分逆序回去
		slow = temp.next;
		temp.next = null;
		while (slow != null) {
			fast = slow.next;
			slow.next = temp;
			temp = slow;
			slow = fast;
		}

		return result;
	}
}
